1. Field of the Invention
The present invention is related to the field of computer systems. Specifically, the present invention relates to cost-based heuristic instruction scheduling for a pipelined processor.
2. Art Background
Instruction scheduling is a technique to significantly reduce the number of execution time pipeline interlocks for a basic block of instructions, and thereby improve the execution speed of the basic block of instructions. Generally, there are three approaches to reducing the number of pipeline interlocks in executing a basic block of instructions, distinguished by the agent and the timing:
a. by the hardware during execution, PA1 b. by the programmer during coding, PA1 c. by the software during compilation. PA1 a. whether an instruction interlocks with any of its immediate successor instructions, PA1 b. the number of immediate successor instructions of the instruction, PA1 c. the length of the longest path from the instruction to the leaves of the dependency graph. PA1 a. there is limited interaction between the heuristics, except as secondary tie breakers, PA1 b. a small difference in a slightly more important heuristic may outweigh a large difference in a slightly less important heuristic. PA1 As will be described, the present invention overcomes the disadvantages of the prior art, and provides an improved method and apparatus for cost-based heuristic instruction scheduling for a pipelined processor.
The hardware approach, while reasonably effective, is very expensive. The hardware approach is also limited to relatively small blocks of instructions. For further description on instruction scheduling via hardware, see Thornton, J. E., Parallel Operation in the Control Data 6600, Proceeding Fall Joint Computer Conference, Part 2, Vol 26, 1964, pp. 33-40, and Tomasuto, R. M., An Efficient Algorithm for Exploiting Multiple Arithmetic Units, IBM Journal of Research and Development, Vol 11, No. 1, January, 1967, pp. 25-33.
It has been found that the programmer approach is, in general, impractical, since it is very time consuming and error-prone. For further description on coding guidelines to avoid pipeline interlocks for assembly language programmers, see Rymarczyk, J. W., Coding Guidelines for Pipelined Processors, Proceeding of the Symposium on Architectural Support for Programming Languages and Operating Systems, Palo Alto, Calif. March, 1982, pp 12-19.
The software approach, particularly at compile time, to detect and remove interlocks, is at present, the most practical and effective approach. Earlier techniques tend to concentrate on the scheduling and compacting of microcode, packing a correct sequence of vertical microinstructions into a shorter sequence of horizontal microinstructions. Other techniques concentrated on scheduling during or after code generation. To date, empirical evidence suggests that heuristic instruction scheduling after code generation is more effective than the other techniques. For a survey of various techniques, see Gross, T. R., Code Optimization of Pipeline Constraints, Technical Report, 83-255, Computer Systems Lab., Stanford University, December, 1983.
In Code Optimization of Pipeline Constraints, Gross described a heuristic scheduling technique that uses look ahead to avoid deadlock, with a worst case complexity of n.sup.4. By using a dependency graph representation and three heuristics in place of look ahead, Gibbons and Muchnick developed a heuristic scheduling technique with an improved worst case complexity of n.sup.2 (linear in practice). Candidate instructions (instructions with no dependency) are analyzed in pairs. A candidate instruction is scheduled if it has a distinguishable difference over the other candidate instructions, in one of the three heuristics which are examined in orders of importance. The three heuristics are:
For further information on Gibbons and Muchnick's technique, see Gibbons P. B. and Muchnick S. S., Efficient Instruction Scheduling for a Pipelined Architecture, Proceedings of the SIGPLAN '86 symposium on compiler construction, July, 1986.
It has been found that the Gibbons and Muchnick technique and its progenies with added number of heuristics have at least two disadvantages: